package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/28 11:15
 * @description：https://leetcode-cn.com/problems/concatenated-words/
 */
public class 连接词 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.findAllConcatenatedWordsInADict(new String[]
                {"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"}));
    }

    /*class Solution {
        Trie root = new Trie();

        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            List<String> ans = new ArrayList<>();
            Arrays.sort(words, Comparator.comparingInt(String::length));
            for (String word : words) {
                if (word.length() == 0) continue;
                if (dfs(word, 0)) {
                    ans.add(word);
                } else {
                    root.insert(word);
                }
            }
            return ans;
        }

        private boolean dfs(String word, int start) {
            if (word.length() == start) return true;
            Trie node = root;
            for (int i = start; i < word.length(); i++) {
                char ch = word.charAt(i);
                node = node.children.get(ch);
                if (node == null) {
                    return false;
                }
                if (node.isEnd) {
                    if (dfs(word, i + 1)) {
                        return true;
                    }
                }
            }
            return false;
        }

        class Trie {
            private boolean isEnd;
            Map<Character, Trie> children;

            public Trie() {
                isEnd = false;
                children = new HashMap<>();
            }

            public void insert(String word) {
                Trie cur = this;
                for (char c : word.toCharArray()) {
                    if (!cur.children.containsKey(c)) {
                        cur.children.put(c, new Trie());
                    }
                    cur = cur.children.get(c);
                }
                cur.isEnd = true;
            }

        }
    }*/

    class Solution {
        Trie root = new Trie();
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            List<String> ans = new ArrayList<>();
            Arrays.sort(words, Comparator.comparingInt(String::length));
            for (String word : words) {
                if (word.length() == 0) continue;;
                if (dfs(word, 0)) {
                    ans.add(word);
                } else {
                    insert(word);
                }
            }
            return ans;
        }

        private boolean dfs(String word, int start) {
            if (start == word.length()) return true;
            Trie node = root;
            for (int i = start; i < word.length(); i++) {
                int index = word.charAt(i)- 'a';
                node = node.children[index];
                if (node == null) return false;
                if (node.isEnd) {
                    if (dfs(word, i + 1)) {
                        return true;
                    }
                }
            }
            return false;
        }


        public void insert(String word) {
            Trie cur = root;
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (cur.children[index] == null) {
                    cur.children[index] = new Trie();
                }
                cur = cur.children[index];
            }
            cur.isEnd = true;
        }

    }

    class Trie {
        public boolean isEnd;
        public Trie[] children;

        public Trie() {
            this.isEnd = false;
            this.children = new Trie[26];
        }
    }
}
